package com.jin.one;

import java.util.ArrayList;
import java.util.Scanner;

/**
 * 快速排序
 * @author Jin
 * @time 2012-12-4下午9:57:18
 */
public class QuickSort {
	static int count=0;
	public static void main(String[] args) {
		while(true){
			System.out.println("\n请输入一组整数，以空格隔开，非数字字符结束，按Enter查看结果：");
			Scanner scan=new Scanner(System.in);
			ArrayList<Integer> list=new ArrayList<Integer>();
			while(scan.hasNextInt()){
				list.add(scan.nextInt());
			}
			int[] arr=new int[list.size()];
			for(int j=0;j<arr.length;j++){
				arr[j]=(Integer)list.get(j);
			}
			sort(arr);
			for(int i=0;i<arr.length;i++){
				System.out.print(arr[i]+"\t");
			}
			System.out.println("完成此次排序的比较次数是："+count);
		}
	}
	public static void sort(int[] data) {
        quickSort(data,0,data.length-1);        
    }
    private static void quickSort(int[] data,int i,int j){
        int pivotIndex=(i+j)/2;
        swap(data,pivotIndex,j);
        int k=partition(data,i-1,j,data[j]);
        swap(data,k,j);
        if((k-i)>1) quickSort(data,i,k-1);
        if((j-k)>1) quickSort(data,k+1,j);
        count++;
    }
    private static int partition(int[] data, int l, int r,int pivot) {
        do{
           while(data[++l]<pivot);
           while((r!=0)&&data[--r]>pivot);
           swap(data,l,r);
        }
        while(l<r);
        swap(data,l,r);        
        return l;
    }
    public static void swap(int[] data, int i, int j) {
        int temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }
}
